package _2021;


import java.util.Arrays;


/**
 * @author ShadowLim
 * @create 2022-03-29-17:18
 */
public class 路径 {
    static int[][] e = new int[2022][2022];
    static int[] dist = new int[2022];
    static boolean[] vis = new boolean[2022];

    public static void main(String[] args) {
        Arrays.fill(dist, Integer.MAX_VALUE);
        for (int i = 1; i <= 2021; i++) {
            for (int j = 1; j <= 2021; j++) {
                if (i == j) {
                    e[i][j] = 0;
                } else {
                    if (Math.abs(i - j) <= 21) {
                        e[i][j] = (i * j) / gcd(i, j);  // 最小公倍数
                    } else {
                        e[i][j] = Integer.MAX_VALUE;
                    }
                }
            }
        }
        dist[1] = 0;
        // Dijkstra
        for (int i = 1; i <= 2021; i++) {
            int u = 0, min = Integer.MAX_VALUE;
            for (int j = 1; j <= 2021; j++) {
               if (!vis[j] && dist[j] < min) {
                   min = dist[j];
                   u = j;
               }
            }
            vis[u] = true;
            for (int j = 1; j <= 2021; j++) {
                if (e[u][j] != Integer.MAX_VALUE && dist[u]+ e[u][j] < dist[j]) {
                    dist[j] = dist[u] + e[u][j];
                }
            }
        }
        System.out.println(dist[2021]);
    }

    private static int gcd(int i, int j) {
        return j == 0 ? i : gcd(j, i % j);
    }
}
